package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/extract-kth-character-from-the-rope-tree'>从 Rope 树中提取第 K 个字符(Extract Kth Character From The Rope Tree)</a>
 * <p>
 * 给定一个二叉树的根节点 root 和整数 k。除了左右孩子之外，该树的每个节点还有另外两个属性：一个仅包含小写英文字母（可能为空）的 字符串 node.val 和一个非负整数 node.len。这棵树中有两种类型的节点：
 *     <ul>
 *         <li>叶子节点：这些节点没有子节点，node.len = 0，node.val 是一个 非空 字符串。</li>
 *         <li>内部节点：这些节点至少有一个子节点（最多两个子节点），node.len > 0，node.val 是一个 空 字符串。</li>
 *     </ul>
 * </p>
 * <p>
 *     上述描述的树被称为 Rope 二叉树。现在我们用以下递归方式定义 S[node]：
 *     <ul>
 *         <li>如果 node 是一个叶子节点，则 S[node] = node.val，</li>
 *         <li>否则，如果 node 是一个内部节点，则 S[node] = concat(S[node.left], S[node.right])，且 S[node].length = node.len。</li>
 *     </ul>
 * </p>
 * <p>返回字符串 S[root] 的第 k 个字符。</p>
 * <p>注意：如果 s 和 p 是两个字符串，则 concat(s, p) 是将字符串 p 连接到 s 后面的字符串。例如，concat("ab", "zz") = "abzz"。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：root = [10,4,"abcpoe","g","rta"], k = 6
 *                           10
 *                        /     \
 *                      4      abcpoe
 *                    /  \
 *                   g   rta
 *      输出："b"
 *      解释：S[root] = concat(concat("g", "rta"), "abcpoe") = "grtaabcpoe"。因此，S[root][5]，表示它的第6个字符，等于 "b"。
 *
 *  示例 2：
 *      输入：root = [12,6,6,"abc","efg","hij","klm"], k = 3
 *                               12
 *                            /     \
 *                           6       6
 *                         /  \     /  \
 *                       abc  efg hij  klm
 *      输出："c"
 *      解释：S[root] = concat(concat("abc", "efg"), concat("hij", "klm")) = "abcefghijklm"。因此，S[root][2]，表示它的第3个字符，等于 "c"。
 *
 *  示例 3：
 *      输入：root = ["ropetree"], k = 8
 *      输出："e"
 *      解释：S[root] = "ropetree"。因此，S[root][7]，表示
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>这棵树的节点数量在区间 [1, 10^3]</li>
 *     <li>node.val 仅包含小写英文字母</li>
 *     <li>0 <= node.val.length <= 50</li>
 *     <li>0 <= node.len <= 10^4</li>
 *     <li>对于叶子节点， node.len = 0 且 node.val 是非空的</li>
 *     <li>对于内部节点， node.len > 0  且 node.val 为空</li>
 *     <li>1 <= k <= S[root].length</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/19 15:42
 */
public class LC2689ExtractKthCharacterFromTheRopeTree_S {
    static class Solution {

        /**
         * 从上往下 - 递归
         */
        public char getKthCharacter(RopeTreeNode root, int k) {
            // base case
            if (root.len == 0) {
                return root.val.charAt(k - 1);
            }
            int leftL = root.left == null ? 0 : Math.max(root.left.len, root.left.val.length());
            // leftL >= k：在左树中继续查找；否在在右树中查找
            return leftL >= k ? getKthCharacter(root.left, k) : getKthCharacter(root.right, k - leftL);
        }

        /**
         * 从上往下 - 迭代
         */
        public char getKthCharacter2(RopeTreeNode root, int k) {
            // base case:root.len==0
            while (root.val.length() > 0) {
                 int leftLen = root.left == null ? 0 : Math.max(root.left.len, root.left.val.length());
                if (leftLen >= k) {
                    root = root.left;
                } else {
                    root = root.right;
                    k += leftLen;
                }
            }
            return root.val.charAt(k - 1);
        }

        /**
         * 从下往上。先拼接出字符串再返回指定字符
         */
        public char getKthCharacter3(RopeTreeNode root, int k) {
            return dfs(root).charAt(k - 1);
        }

        private String dfs(RopeTreeNode root) {
            if (root == null) {
                return "";
            }
            // 叶子节点。这些节点没有子节点，node.len = 0，node.val 是一个 非空 字符串。
            if (root.len == 0) {
                return root.val;
            }
            // 内部节点。这些节点至少有一个子节点（最多两个子节点），node.len > 0，node.val 是一个 空 字符串。
            // 连接左子树和右子树的结果并返回。 61
            return dfs(root.left) + dfs(root.right);
        }
    }

    static class RopeTreeNode {
        int len;
        String val;
        RopeTreeNode left;
        RopeTreeNode right;

        RopeTreeNode() {
        }

        RopeTreeNode(String val) {
            this.len = 0;
            this.val = val;
        }

        RopeTreeNode(int len) {
            this.len = len;
            this.val = "";
        }

        RopeTreeNode(int len, RopeTreeNode left, RopeTreeNode right) {
            this.len = len;
            this.val = "";
            this.left = left;
            this.right = right;
        }
    }
}
